package find;

import java.util.HashMap;

/**
 * 获取添加的字符串中出现次数最多的前K个
 * 是动态的不是一下添加完,随时添加随时获取，
 * 如果是一下给完，可以用大小K的堆一下获取完
 *
 * @author Liaorun
 */
public class TopK {

    public static void main(String[] args) {
        TopKRecord topKRecord = new TopKRecord(2);

        topKRecord.addAll("abc", "a", "ac", "ab", "abc");

        topKRecord.printTopK();
    }


    public static class Node {
        public String str;
        public int times;

        public Node(String s, int t) {
            str = s;
            times = t;
        }
    }


    public static class TopKRecord {
        private Node[] heap;
        /**
         * 堆上元素的个数
         */
        private int size;
        // 添加过的字符串的词频表
        private HashMap<String, Node> strNodeMap;
        // 节点在堆上的位置
        private HashMap<Node, Integer> nodeIndexMap;

        public TopKRecord(int size) {
            heap = new Node[size];
            this.size = 0;
            strNodeMap = new HashMap<>();
            nodeIndexMap = new HashMap<>();
        }


        public void addAll(String... strings) {
            for (String s : strings) {
                add(s);
            }
        }

        public void add(String str) {
            Node curNode = null;
            int preIndex = -1;

            if (!strNodeMap.containsKey(str)) {
                // 没有添加过的字符串，第一次添加
                curNode = new Node(str, 1);
                // 添加到词频表
                strNodeMap.put(str, curNode);
                // 当前节点没有在堆上，用-1的位置表示
                nodeIndexMap.put(curNode, -1);
            } else {
                // 已经添加过的字符串，获取记录的词频
                curNode = strNodeMap.get(str);
                curNode.times++;
                preIndex = nodeIndexMap.get(curNode);
            }

            if (preIndex == -1) {
                // 当前节点没有在堆上
                if (size == heap.length) {
                    // 堆的节点数量等于K
                    if (heap[0].times < curNode.times) {
                        // 满足了门槛，当前节点出现的次数 > 小根堆根节点的次数
                        // 小根堆弹出栈顶，添加当前元素到栈顶，在堆化
                        nodeIndexMap.put(heap[0], -1);
                        nodeIndexMap.put(curNode, 0);
                        heap[0] = curNode;
                        heapify(0, size);
                    }
                } else {
                    // 堆的数量没有等于K
                    // 直接添加当前节点到堆尾上
                    nodeIndexMap.put(curNode, size);
                    heap[size] = curNode;
                    // 上浮堆化
                    heapInsert(size++);
                }
            } else {
                // 已经添加过的字符串 且 节点也在堆上
                // 前面已经添加过词频了，下沉堆化一下就行了
                heapify(preIndex, size);
            }
        }

        private void heapInsert(int index) {
            while (index != 0) {
                // 父节点的位置 = （当前位置 - 1）/ 2
                int parent = (index - 1) / 2;
                if (heap[index].times < heap[parent].times) {
                    // 父节点大需要交换
                    swap(parent, index);

                    // 父节点成为下一轮的当前节点
                    index = parent;
                } else {
                    // 父节点比当前节点小 or ==，上浮堆化完成，直接节点循环
                    break;
                }
            }
        }

        /**
         * 交换堆上的两个元素，同时更新位置记录
         *
         * @param a
         * @param b
         */
        private void swap(int a, int b) {
            nodeIndexMap.put(heap[a], b);
            nodeIndexMap.put(heap[b], a);

            Node temp = heap[a];
            heap[a] = heap[b];
            heap[b] = temp;
        }

        /**
         * 下沉堆化，小根堆，父节点比子节点大就交换
         *
         * @param index 开始检查的元素
         * @param size  堆的长度 or 结束位置
         */
        private void heapify(int index, int size) {
            int l = index * 2 + 1;
            int r = index * 2 + 2;

            int smallest = index;

            // 跳出条件:没有左节点
            while (l < size) {
                if (heap[l].times < heap[index].times) {
                    smallest = l;
                }

                if (r < size && heap[r].times < heap[index].times) {
                    smallest = r;
                }

                // 最小
                if (smallest != index) {
                    swap(smallest, index);
                } else {
                    // 当前节点比子节点都小，下沉堆化完成，直接结束循环
                    break;
                }

                index = smallest;

                l = index * 2 + 1;
                r = index * 2 + 2;
            }
        }

        public void printTopK() {
            for (int i = 0; i < heap.length; i++) {
                if (heap[i] == null) {
                    break;
                }
                System.out.println("heap[i].str = " + heap[i].str);
                System.out.println("heap[i].times = " + heap[i].times);
            }
        }

        public Node[] getTopK() {
            return heap;
        }
    }
}
